#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#include <sstream>
#include <stdexcept>
#include <string>
#include <fstream>
using namespace std;

#define used 1
#define open 0
#define deleted -1
/*prime > 2* 100,000*/
int size = 393241;

#ifndef DATA_VAL
#define DATA_VAL
/*hash table item type*/
struct data_val
{
  //key
  string string_data; 
  //value to store
  vector<int> value ;
  //number of data a key maps to
  int value_size;
  //deleted? open? used?
  int status;
	
  data_val()
  {
    string_data ="";
    value_size = 0;
    value.clear();
    //start with status open
    //assumes value.clear() sets everything to 0 - not sure
    status = 0;  
  }
};
#endif

int num_collusions = 0;
#ifndef HASH_DATA
#define HASH_DATA
/*hash table item type*/
struct hash_data
{
	string key;
	int old_hash;
	int new_hash;
	
	
  hash_data()
  {
    key="";
	old_hash =0;
	new_hash =0;
  }
  hash_data(const string &s, const int &oldH, const int &newH)
  {
	key = s;
	old_hash = oldH;
	new_hash = newH;
  }
};
#endif

vector<hash_data> hash_table_data;

#ifndef HASHTABLE_H
#define HASHTABLE_H
template <typename T>
class Hashtable{
 public: 
  Hashtable();
  ~Hashtable();
  /*Hashes a key(s) and stores data(i)*/
  void insert(string s, int i);
  /*rehashes str and retreves value*/
  void query(string str,ostream &out);

 private:
  /*Hash function by Daniel J. Bernstein - supposedly best for string hashing*/
  unsigned int DJB_Hash_Func(const std::string& str) ;
  /*Quadratic probing during collusion*/
  unsigned int quadratically_prob(const unsigned int hash);

  /*the hash table*/
  vector<data_val> hash_table;
  /*number of items inserted into hash_table - unique*/
  int hashtable_size; 
};
#endif

template <class T>
Hashtable<T>::Hashtable()
{
	/*Going to do quadratic probing
	to prevent too much collusions and tight packing hash table size 
    needs to be prime and 2*size.therefore the next prime 
    above 2 * 100,000 is 393,241. It has lower bound 2^18 and upper 2^19 and  the relative deviation 
	(in percent) of the prime number from the optimal middle of 2^18 and 2^19 is 0.006358
	http://planetmath.org/encyclopedia/GoodHashTablePrimes.html */
	
  hashtable_size = 0;
  hash_table.resize(size);    
  hash_table.clear();
}

template <class T>
Hashtable<T>::~Hashtable()
{
  hash_table.clear();
}

template <class T>
void Hashtable<T>::insert(string s, int i)
{
  int step =0;
  int checksum = DJB_Hash_Func(s);
  if(hash_table[checksum].status == open || hash_table[checksum].string_data == s)
    {
      if(hash_table[checksum].string_data ==s)
        {
          hash_table[checksum].value.push_back(i);
          hash_table[checksum].value_size++;
        }
      else
        {
          hash_table[checksum].string_data = s;
          hash_table[checksum].value.push_back(i);
          hash_table[checksum].value_size++;
          hash_table[checksum].status = used;
          hashtable_size++;
        }
    }
}

template <class T>
unsigned int Hashtable<T>::quadratically_prob(const unsigned int hash)
{
  int step = 0;
  unsigned int new_hash = hash;
  while(hash_table[new_hash].status == used)
    {
      step++;
      new_hash = (new_hash + step*step);
	  if(new_hash>size)
		new_hash = new_hash%size;		
      //cout<<new_hash<<endl;
	}
  return new_hash;
}
/*
  Code for DJB_Hash_function is from 
  http://www.cse.yorku.ca/~oz/hash.html and
  http://wizardsoweb.com/djb-hash-program-and-algorithm/2011/05/
  It has been modifed as needed for this lab/project
*/
template <class T>
unsigned int Hashtable<T>:: DJB_Hash_Func(const std::string& str)
{
  /*in my one day of reserch could not find why 5381
  or how this hash is working and reasons for the numbers chosen*/
  
   int hash = 5381;
   for(size_t i = 0; i < str.length(); i++)
      hash = ((hash<< 5) + hash) + str[i];   
	if(hash<0)
		hash = -1 *hash;
   //check if hash result is above bucket size
   //if so wrap arround
	if(hash > size)
		hash = hash%size;
				
   //if position is occupied quadratically prob for next location
   if(hash_table[hash].status == used && 
      hash_table[hash].string_data != str){
		num_collusions++;
		int newhash = quadratically_prob(hash);
	
		hash_data k(str,hash,newhash);
	
		hash_table_data.push_back(k);
	return newhash;
   }
   return hash;
}
/*helper function - change int to string*/
string IntToString(int n)
{
  ostringstream result;
  result <<n;
  return result.str();
}

template <class T>
void Hashtable<T>::query(string str,ostream &out)
{
  string temp="",temp2="";
  unsigned int hash = DJB_Hash_Func(str);

  if(hash_table[hash].string_data ==str)
    {
      for(int j = 0; j < hash_table[hash].value_size; j++)
        {
          temp.append(IntToString(hash_table[hash].value[j]));
          temp.append(", ");
          temp2.append(temp);
          temp="";
        }
      temp2 = temp2.substr(0,temp2.length()-2);
      out<<temp2<<endl;
      temp2="";
    }
  else
    out<<"item not in hash table"<<endl;
}

int get_collusions()
{
	return num_collusions;
}

void print_data(ostream &out)
{
	out<<endl;
	out<<"\t\t\t Collusion data Summary"<<endl;
	out<<"#\t"<<"\tKEY\t"<<"\tOriginal Hash\t"<<"\tnew Hash\t"<<endl;
	for(int j = 0; j < num_collusions; j++)
        {
			out<<j<<"\t"<<hash_table_data[j].key<<"\t"<<hash_table_data[j].old_hash<<"\t"<<hash_table_data[j].new_hash<<"\t"<<endl;
		 }
}



